#include "ghost.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

// 方向数组：上、下、左、右
static const int dx[] = {-1, 1, 0, 0};
static const int dy[] = {0, 0, -1, 1};

void ghost_init(Ghost* ghost, int startRow, int startCol) {
    ghost->row = startRow;
    ghost->col = startCol;
    ghost->targetRow = startRow;
    ghost->targetCol = startCol;
}

// 只把墙当障碍
static int is_walkable(Map* map, int row, int col) {
    if (row < 0 || row >= MAP_ROWS || col < 0 || col >= MAP_COLS) return 0;
    return map->grid[row][col] != WALL;
}

// 标准BFS追踪Pacman
static int find_path(Map* map, int startRow, int startCol, int targetRow, int targetCol, int* nextRow, int* nextCol) {
    if (startRow == targetRow && startCol == targetCol) return 0;
    Queue queue;
    queue_init(&queue);
    int visited[MAP_ROWS][MAP_COLS] = {0};
    int parent[MAP_ROWS][MAP_COLS][2];
    for (int i = 0; i < MAP_ROWS; i++)
        for (int j = 0; j < MAP_COLS; j++)
            parent[i][j][0] = parent[i][j][1] = -1;

    queue_enqueue(&queue, startRow, startCol);
    visited[startRow][startCol] = 1;
    int found = 0;
    while (!queue_is_empty(&queue)) {
        int r, c;
        queue_dequeue(&queue, &r, &c);
        if (r == targetRow && c == targetCol) {
            found = 1;
            break;
        }
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d];
            int nc = c + dy[d];
            if (is_walkable(map, nr, nc) && !visited[nr][nc]) {
                queue_enqueue(&queue, nr, nc);
                visited[nr][nc] = 1;
                parent[nr][nc][0] = r;
                parent[nr][nc][1] = c;
            }
        }
    }
    queue_free(&queue);
    if (!found) return 0;
    // 回溯路径，找到起点的下一个格子
    int pr = targetRow, pc = targetCol;
    int path[MAP_ROWS * MAP_COLS][2];
    int len = 0;
    while (!(pr == startRow && pc == startCol)) {
        path[len][0] = pr;
        path[len][1] = pc;
        int tmpR = parent[pr][pc][0];
        int tmpC = parent[pr][pc][1];
        pr = tmpR;
        pc = tmpC;
        len++;
    }
    // 路径长度至少为1
    if (len == 0) return 0;
    *nextRow = path[len-1][0];
    *nextCol = path[len-1][1];
    return 1;
}

void ghost_move(Ghost* ghost, Map* map, Pacman* pacman) {
    int nextRow, nextCol;
    int found = find_path(map, ghost->row, ghost->col, pacman->row, pacman->col, &nextRow, &nextCol);
    if (found) {
        map->grid[ghost->row][ghost->col] = EMPTY;
        ghost->row = nextRow;
        ghost->col = nextCol;
        map->grid[ghost->row][ghost->col] = GHOST;
    }
}

void ghost_draw(Ghost* ghost, Map* map) {
    map->grid[ghost->row][ghost->col] = GHOST;
}

int ghost_collision(Ghost* ghost, Pacman* pacman) {
    return ghost->row == pacman->row && ghost->col == pacman->col;
} 